package org.shj.algorithm.string;

/**
 * 编辑距离，也叫 Levenshtein 距离。是指两个字符串之间，由一个变成另一个，
 * 最少需要多少次编辑。允许的编辑操作有：
 * 1. 插入一个字符
 * 2. 替换一个字符
 * 3. 删除一个字符
 *
 * 实际应用：拼写纠错、计算字符串相似度
 *
 * 解题思路：
 *    记两字符串为A，B。 lev(A,B) 表示两个字符串的编辑距离。假设从A 变成 B
 *    A[1...lenA] 表示 A 字符串从第一位(包含)到最后一位(包含)，则 A[2...lenA] 表
 *    示一个字符串，其值是取 A 中第二位开始一直到最后一位
 *
 * 1. 如果第一个字符相等，则lev(A,B) = lev(A[2...lenA], B[2...lenB]
 * 2. 如果第一个字符不相等
 *    (a) A 的第一个字符替换成 B 的第一个字符，则 lev(A,B) = lev(A[2...lenA], B[2...lenB] + 1
 *    (b) 删除 A 的第一个字符，则 lev(A,B) = lev(A[2...lenA], B[1...lenB] + 1
 *    (c) B 的第一个字符插入到A，则 lev(A,B) = lev(A[1...lenA], B[2...lenB] + 1
 * 3. 取(a),(b),(c) 中的最小的值
 *
 * 根据上面的分析，很容易想到递归去做。字符串较多时，递归栈较深。我们可以用动态规划的方法去做。
 * 建立动态规划方程：
 * 建立一个二维数组： 数组中的值edit[i][j] 表示 A 的前 i 个字符和 B 的前 j 个字符的编辑距离。
 * 如果 A[i]=B[j]，则 edit[i][j] = edit[i-1][j-1]
 * 如果 A[i]!=B[j], 则 edit[i][j] = min(edit[i-1][j-1],edit[i][j-1],edit[i-1][j]) + 1
 *
 * @author Shen Huang Jian
 * @date 2019-01-24 8:53
 */
public class EditDistance {

    public static void main(String[] args){
        String a = "algorithm";
        String b = "altruistic";
        System.out.println(calcEditTimes(a, b));
        System.out.println(dongGui(a,b));
    }

    private static int dongGui(String a, String b){
        int edit[][] = new int[a.length()+1][b.length()+1];
        //初始化第一行第一列的值，分别代表某个字符串为空时，
        //相应的编辑距离即是另一个字符串的长度
        for(int i = 0; i < a.length()+1; i++){
            edit[i][0] = i;
        }
        for(int j = 0; j < b.length()+1; j++){
            edit[0][j] = j;
        }

        for(int i = 1; i < a.length()+1; i++){
            for(int j = 1; j < b.length()+1; j++){
                if(a.charAt(i - 1) == b.charAt(j - 1)){
                    edit[i][j] = edit[i-1][j-1];
                }else{
                    int min = edit[i-1][j-1] < edit[i][j-1] ? edit[i-1][j-1] : edit[i][j-1];
                    min = min < edit[i-1][j] ? min : edit[i-1][j];
                    edit[i][j] = min + 1;
                }
            }
        }
        return edit[a.length()][b.length()];
    }

    //递归方式，这里是从最后一位开始比较的。
    private static int calcEditTimes(String a, String b){
        if("".equals(a)){
            return b.length();
        }
        if("".equals(b)){
            return a.length();
        }
        int aLastIndex = a.length() - 1;
        int bLastIndex = b.length() - 1;
        if(a.charAt(aLastIndex) == b.charAt(bLastIndex)){
            return calcEditTimes(a.substring(0, aLastIndex), b.substring(0, bLastIndex));
        }else{
            int lenReplace = 1 + calcEditTimes(a.substring(0, aLastIndex), b.substring(0, bLastIndex));
            int lenDel = 1+calcEditTimes(a, b.substring(0, bLastIndex));
            int lenInsert = 1+calcEditTimes(a.substring(0, aLastIndex), b);
            int min = lenDel > lenReplace ? lenReplace : lenDel;
            return min < lenInsert ? min : lenInsert;

        }

    }
}
